package org.kfive.nova.algorithm.sort;

/**
 * Created with IntelliJ IDEA.
 * User: admin
 * Date: 14-5-14
 * Time: 上午9:32
 * To change this template use File | Settings | File Templates.
 */
public class HeapSort {

    public static void adjustHeap(int [] source,int i,int n){
        if(source!=null&&source.length>0){
            int j;
            j = 2*i+1;
            int temp = source[i];
            while (j<n){
                if(j+1<n&&source[j+1]<source[j]){
                    j++;
                }
                if(source[j]>=temp){
                    break;
                }
                source[i]=source[j];
                i=j;
                j=2*i+1;
            }
            source[i]=temp;
        }

    }

    public static  void buildHeap(int source[]){
        for (int i=source.length/2-1;i>=0;i--){
            adjustHeap(source,i,source.length);
        }

    }

    public static void heapSort(int []source){
        buildHeap(source);
        for(int i =source.length-1;i>0;i--){
            int temp = source[0];
            source[0] = source[i];
            source[i]=temp;
            adjustHeap(source,0,i);
        }
    }

    public static void main(String [] args){
        int [] source = {8,3,6,8,1,2,0,4,1,56,78,123,45,98};
        heapSort(source);
        for (int i=0;i<source.length;i++){
            System.out.println(source[i]);
        }
//        Queue queue = new quere
    }
}
